package com.doitedu.day02

/**
 * @Date 22.6.20
 * @Created by HANGGE
 * @Description
 *             定义一个方法  二分查找
 * 对有序的数据进行快速检索
 *   实现思路就是 从中间获取值  和要找的值对比
 *    中间的值  >  要找的值   要找的数据在中间值的左边 (去重一半的数据范围)
 *    中间的值  <  要找的值   要找的数据在中间值的右边 (去重一半的数据范围)
 *    依次类推 快速定位数据的位置
 */
object _02二分查找 {
  def main(args: Array[String]): Unit = {
    val array = Array[String]("changruiming" , "liuyong" , "pengweihao" ,"wuyifu", "zhouyangzhu")

    val index = binarySeacher(array, "wuyifu")
    println(index)

  }

  /**
   *  如果有个东西可以帮助我们额外的描述 T (可排序的)  隐式
   * @param arr  [升序] 必须是有序集合 ,如果集合没有顺序 , 你会查个寂寞
   * @param name
   * @return
   */
  def binarySeacher(arr:Array[String] , name:String): Int ={
    if (arr == null || arr.length <= 0){
      return -1
    }
    // 确定查找数据的范围
    var  start = 0
    var  end = arr.length - 1
    while (start <= end ){
      // 获取中间的数据
      var midd = (start+end) / 2
      // 获取的当前的中间值数据
      val getValue = arr(midd)
      if (getValue > name){
         end = midd -1
      }else if (getValue < name){
        start = midd + 1
      }else{
        // 找到的数据位置
        return midd
      }
    }
    -1
  }



  /**
   *  如果有个东西可以帮助我们额外的描述 T (可排序的)  隐式
   * @param arr  [升序] 必须是有序集合 ,如果集合没有顺序 , 你会查个寂寞
   * @param name
   * @return
   */
  def binarySeacher(arr:Array[Int] , name:Int): Int ={
    if (arr == null || arr.length <= 0){
      return -1
    }
    // 确定查找数据的范围
    var  start = 0
    var  end = arr.length - 1
    while (start <= end ){
      // 获取中间的数据
      var midd = (start+end) / 2
      // 获取的当前的中间值数据
      val getValue = arr(midd)
      if (getValue > name){
        end = midd -1
      }else if (getValue < name){
        start = midd + 1
      }else{
        // 找到的数据位置
        return midd
      }
    }
    -1
  }





}
